\parskip 12 pt
\parindent 0 pt
\magnify {1100}
\centerline{\bf CS154, PROBLEM SET 7, SOLUTIONS}

6.3

Everyone knew how to do this one, but about half of the class got it
wrong out of apparent carelessness.  You need to apply Ogden's lemma
to the string $a↑{n}b↑{n}c↑{n!+n}$, not $a↑{n}b↑{n}c↑{n!}$ as hinted
in the text.

6.4 (b)

Solution 1:  Pass the language, $L$, through a GSM that outputs
(non-deterministically) a random prefix of its input.  This generates
INIT($L$).  Since CFLs are closed under GSM transformations,
INIT($L$) is a CFL.  (The required GSM reads characters and writes
them back out until it takes an epsilon transition to a state where
it reads characters and outputs nothing.  All states of the GSM
are accepting.)

Solution 2:  Work directly with a grammar.  Delete $ε$ from the language
if it is present, and then convert the language to CNF to facilitate the
discussion (it is possible to construct INIT($L$) without first converting
to CNF).  We construct $G↑{\prime}$ (with start symbol, $S↑{\prime}$) as follows:
Include all productions of $G$ in $G↑{\prime}$.  For every variable, $A$,
in $G$, include the production, $A↑{\prime} → A$, in $G↑{\prime}$.
For every production of the form $A → a$ in $G$ include the production,
$A↑{\prime} → ε$, in $G↑{\prime}$.  For every production of the
form $A → BC$ in $G$, include the production, $A↑{\prime} →
B↑{\prime} \mid BC↑{\prime} \mid ε$, in $G↑{\prime}$.  (Since there
are no useless symbols in $G$, that last $ε$ was not necessary.)
$G↑{\prime}$ is a grammar for INIT($L$).

Solution 3:  Work directly with PDAs.  Let $M$ be a machine that accepts
$L$.  Let $M↓{1}$ be the machine obtained by labelling all transitions
of $M$ with $ε$.  Connect every state of $M$ with the corresponding
state of $M↓{1}$ via an epsilon transition that does not affect the
stack.  The machine so constructed accepts INIT($L$).


Solution 4:  Put $L$ into Greibach Normal Form.  Then remove all useless
symbols.  Construct a PDA, $M$, such that $L$ is N($M$) by the construction
of chapter 5 (it is important to use this particular PDA for $L$).
Because there are no useless sybols in $L$, every transition of $M$
corresponds to a step in the derivation of some string in $L$.  If all
the states of $M$ are considered to be final states, then INIT($L$) is
L($M$).

6.4 (d)

Work directly with the grammar.  Reverse the right-hand-sides
of all productions to obtain a grammar that accepts the reverse.

\vfill\eject

6.16

You can't solve this by just converting the grammar into CNF, because
this will affect which sentential forms are derivable.

Make the following modifications to the given grammar:  Add the new start
symbol, $S↑{\prime}$ and the production $S↑{\prime} → \alpha$.
For each variable $X$ of the grammar, add the new terminal character
$c↓{X}$ and the production $X → c↓{X}$ and replace all occurrences of
$X$ in $\beta$ by $c↓{X}$.  Use CYK to see if this new $\beta$ is derivable
from $S↑{\prime}$ in the modified grammar.  This is true exactly when
the original $\beta$ is derivable from $\alpha$ in the original grammar.

6.17

$A,C$ should appear in all boxes of line 1.  $B$, in all boxes of line 2.
$S,A,C$, in line 3.  $B$, in line 4.  $S,A,C$, in line 5.  Since $aaaaa$ is
derivable from $S$, it is in the language.

\vfill\eject\end